/*
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
*/


#include <iostream>
#include <set>

using namespace std;

int single_number_1(int array[], int size)
{
  cout << "Use set." << endl;
  set<int> mySet;
  for(int i = 0; i < size; i++)
  {
    if(mySet.find(array[i]) != mySet.end())
    {
      //if the integer is in the set, erase it.
      mySet.erase(array[i]);
      cout << "Found " << array[i] << " in mySet. Erased it." << endl;
    }
    else
    {
      //else, insert this integer to the set.
      mySet.insert(array[i]);
    }
  }

  int singleNumber = *mySet.begin();

  return singleNumber;
}

int single_number_2(int array[], int size)
{
  cout << "Use XOR." << endl;
  int singleNumber = 0;

  for(int i = 0; i < size; i++)
  {
    singleNumber = (singleNumber ^ array[i]);
  }

  return singleNumber;
}

int main()
{

  int array[19] = {2, 4, 3, 2, 4, 1, 9, 7, 5, 8, 6, 7, 5, 9, 3, 8, 6};

  //int singleNumber = single_number_1(array, 19);
  int singleNumber = single_number_2(array, 19);

  cout << "The single number is: " << singleNumber << endl;

  return 0;
}
